package hello;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class RedBlackTree<T extends Comparable<T>> {
	
	//定义红黑树的颜色
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	class Node {
		T data;
		Node parent;
		Node left;
		Node right;
		// 节点的默认颜色是黑色
		boolean color = BLACK;
		public Node(T data, Node parent, Node left, Node right) {
			super();
			this.data = data;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}
		
		public String toString() {
			return "[data=" + data + ", color="+ color +"]";
		}
		
		public boolean equals(Object obj) {
			if(this == obj)
				return true;
			if(obj.getClass() == this.getClass()) {
				Node target = (Node) obj;
				return data.equals(target.data)
					&& color == target.color
					&& left == target.left
					&& right == target.right
					&& parent == target.parent;
			}
			return false;
		}
	}
	private Node root;
	// 两个构造器用于创建排序二叉树
	public RedBlackTree(){
		this.root = null;
	}
	
	public RedBlackTree(T o) {
		root = newNode(o);
	}
	
	Node newNode(T o) {
		return new Node(o, null, null, null);
	}
	
	// 添加节点
	public void add(T ele) {
		// 如果节点为null
		if (root == null) {
			root = newNode(ele);
		} else {
			Node current = root;
			Node parent = null;
			int cmp = 0;
			//搜索合适的叶子节点，以该叶子节点为父节点添加新节点
			do {
				parent = current;
				cmp = ele.compareTo(current.data);
				// 如果新节点的值大于当前节点的值
				if(cmp > 0) {
					// 以右子节点作为当前节点
					current = current.right;
				} else { // 如果新节点的值小于当前节点的值
					// 以左子节点为当前节点
					current = current.left;
				}
			} while (current != null);
			// 创建新节点
			Node newNode = new Node(ele, parent, null, null);
			// 如果新节点的值大于父节点的右子节点
			if (cmp > 0) {
				// 新节点作为父节点的右子节点
				parent.right = newNode;
			} else { // 如果新节点的值小于父节点的值
				// 新节点作为父节点的左子节点
				parent.left = newNode;
			}
			// 维护红黑树
//			fixAfterInsertion(newNode);
		}
	}
	
	// 删除节点
	public void remove(T ele) {
		// 获取要删除的节点
		Node target = getNode(ele);
		// 如果被删除节点左子树、右子树都不为空
		if (target.left != null && target.right != null) {
			// 找到target节点中序遍历的前一个节点
			// s用于保存target节点的左子树中值最大的节点
			Node s = target.left;
			// 搜索target节点的左子树中最大的节点
			while(s.right != null) {
				s = s.right;
			}
			// 用s节点来替代p节点
			target.data = s.data;
			target = s;
		}
		// 开始修改它的替换节点，如果该替换节点不为null
		Node replacement = (target.left != null ? target.left : target.right);
		if (replacement != null) {
			// 让replacement 的parent指向target的parent
			replacement.parent = target.parent;
			// 如果target的parent为null，表面target本身是根节点
			if (target.parent == null) {
				root = replacement;
				//如果target 是其父节点的左子节点
			} else if (target == target.parent.left) {
				// 让target的父节点left指向replacement
				target.parent.left = replacement;
			} else { // 如果target是其父节点的右子节点
				// 让target的父节点right指向replacement
				target.parent.right = replacement;
			}
			// 彻底删除target节点
			target.left = target.right = target.parent = null;
			// 修复红黑树
			if(target.color == BLACK) {
//				fixAfterDeletion(replacement);
			}
		} else if (target.parent == null) {
			root = null;
		} else {
			// target没有子节点，把它当成虚的替代节点
			// 修复红黑树
			if (target.color == BLACK) {
//				fixAfterDeletion(target);
			}
			if (target.parent != null) {
				// 如果target是其父节点的左子节点
				if(target == target.parent.left) {
					// 将target的父节点left设为null
					target.parent.left = null;
				} else { // 如果target是其父节点的左子节点
					// 将target的父节点right设为null
					target.parent.right = null;
				}
				// 将target的parent设置null
				target.parent = null;
			}
		}
	}
	
	// 根据给定的值搜索节点
	public Node getNode(T ele) {
		// 从根节点开始搜索
		Node p = root;
		while(p != null) {
			int cmp = ele.compareTo(p.data);
			// 如果搜索的值小于当前p节点的值
			if (cmp < 0) {
				// 向左子树搜索
				p = p.left;
			} else if(cmp > 0) { // 如果搜索的值大于当前p节点的值
				// 向右子节树搜索
				p = p.right;
			} else { // 如果相等返回这个节点
				return p;
			}
		}
		return null;
	}
	
	// 广度优先遍历
	public List<Node> breadthFirst() {
		Queue<Node> queue = new ArrayDeque<>();
		List<Node> list = new ArrayList<>();
		if (root != null) {
			// 将根元素加入队列
			queue.offer(root);
		}
		while(! queue.isEmpty()) {
			// 将该队列的队尾的元素添加到list中
			Node p = queue.poll();
			list.add(p);
			// 如果左子节点不为null，将它加入队列
			if(p.left != null) {
				queue.offer(p.left);
			}
			// 如果右子节点不为null，将它加入队列
			if (p.right != null) {
				queue.offer(p.right);
			}
		}
		return list;
	}
	
	// 插入节点后修复红黑树
	private void fixAfterInsertion(Node x) {
		x.color = RED;
		// 直到x节点的父节点不是根，且x的父节点不是红色
		while(x != null && x != root && x.parent.color == RED) {
			// 如果x的父节点是其父节点的左子节点
//			if (parentOf(x) == ) {
//				
//			}
		}
	}
	
	// 获取指定节点的颜色
	private boolean colorOf(Node p) {
		return (p == null ? BLACK : p.color);
	}
	// 获取指定节点的父节点
	private Node parentOf(Node p) {
		return (p == null ? null : p.parent);
	}
	
	// 为指定节点设置颜色 
	private void setColor(Node p, boolean c) {
		if (p != null) 
			p.color = c;
	}
	
	// 获取指定节点的左子节点
	private Node leftOf(Node p) {
		return p == null ? null : p.left;
	}
	
	// 获取指定节点的右子节点
	private Node rightOf(Node p) {
		return p == null ? null : p.right;
	}
	
	/**
	 * 执行如下转换
	 * p		r
	 * 	  r  p 
	 * q		q
	 */ 
	private void rotateLeft(Node p) {
		if (p != null) {
			// 获取p的右子节点
			Node r = p.right;
			Node q = r.left;
			// 将r的左子节点的parent指向p节点
			p.right = q;
			// 然r的左子节点的parent指向p节点
			if (q != null) {
				q.parent = p;
			}
			r.parent = p.parent;
			// 如果p已经是根节点
			if (p.parent == null) {
				root = r;
				// 如果p是其父节点的左子节点
			} else if (p.parent.left == p) {
				// 将r设为p的父节点的左子节点
				p.parent.right = r;
			} else {
				// 将r设为p的父节点的右子节点
				p.parent.right = r;
			}
			r.left = p;
			p.parent = r;
		}
	}
	
	/**
	 * 执行如果转换
	 *   p		l
	 * l		  p
	 *    q		q
	 */
	private void rotateRight(Node p) {
		if (p != null) {
			// 取得p的左子节点
			Node l = p.left;
			Node q = l.right;
			// 将l的右子节点链到p的左节点链上
			p.left = q;
			// 让l的右子节点的parent指向p节点
			if (q != null) {
				p.parent = p;
			}
			l.parent = p.parent;
			// 如果p已经是根节点
			if (p.parent == null) {
				root = l;
				// 如果p 是其父节点的右子节点
			} else if(p.parent.right == p) {
				// 将l设为p的父节点的右子节点
				p.parent.right = l;
			} else {
				// 将l设为p的父节点的左子节点
				p.parent.left = l;
			}
			l.right = p;
			p.parent = l;
		}
	}
	
	// 实现中序遍历
	public List<Node> inIterator() {
		return inIterator(root);
	}
	public List<Node> inIterator(Node node) {
		List<Node> list = new ArrayList<>();
		// 递归处理左子树
		if (node.left != null) {
			list.addAll(inIterator(node.left));
		}
		// 处理根节点
		list.add(node);
		// 递归处理右子树
		if (node.right != null) {
			list.addAll(inIterator(node.right));
		}
		return list;
	}
}
